#include <vector>
#include <algorithm>

using namespace std;


class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1, -1);  // 创建动态规划数组
        dp[0] = 0;
        for (int i=1; i<=amount; ++i) {
            int curr = amount + 1;
            for (int j=0; j<coins.size(); ++j) {
                int prev = i - coins[j];  // 子问题下标为 i - coins[j]
                if (prev >= 0 && dp[prev] != -1) {  // 验证 dp[prev] 是否可行
                    curr = min(curr, 1+dp[prev]);
                }
            }
            if (curr < amount + 1) {  // 验证 curr 的值是否合法
                dp[i] = curr;
            }
        }
        return dp[amount];
    }
};
